The present invention relates generally to the design and testing of integrated circuits and other complex electronic circuits, and more particularly to techniques for generating test patterns for use in testing such circuits.
Automatic test pattern generation (ATPG) for sequential circuits is an extremely expensive computational process. ATPG algorithms working on complex sequential circuits can spend many hours of central processing unit (CPU) time and still obtain poor results in terms of fault coverage. There are a number of factors that contribute to the difficulty of the ATPG process for sequential circuits. For example, it is generally necessary for an ATPG algorithm to use a model that includes an iterative array of time frames, where the number of time frames may be, in the worst case, an exponential function of the number of flip-flops (FFs) in the circuit. In addition, an ATPG algorithm may waste a substantial amount of time trying to justify illegal states. Furthermore, an ATPG algorithm typically must complete an exhaustive search for each target fault that is to be identified as untestable.
Because of the above-noted difficulties associated with the sequential ATPG problem, complex sequential circuits are generally tested using design for testability (DFT) techniques, such as scan design, which significantly change the structure of a given circuit so as to make its buried FFs more controllable and observable in test mode. However, scan-type DFT techniques introduce delay penalties that result in performance degradation, and substantially increase circuit area overhead thereby increasing power consumption and decreasing yield. In addition, scan-type DFT techniques are not directly compatible with at-speed testing.
A need therefore exists for techniques for performing ATPG for sequential circuits in a more efficient manner, so as to overcome the problems associated with conventional ATPG, while also avoiding the problems associated with existing DFT techniques such as scan design.
In accordance with one aspect of the invention, test pattern generation is performed for a sequential circuit by first separating the circuit into overlapping pipelines by controlling corresponding clocks for one or more registers of the circuit so as to break feedback loops of the circuit, and then processing each of the pipelines separately in order to determine if particular target faults are detectable in the pipelines. Independent clocks may be provided for each of a number of registers of the circuit, using a clock partitioning technique, in order to facilitate the breaking of the feedback loops for a given pipeline. The feedback loops may be broken by a clock freezing technique which involves freezing one or more of the independent clocks.
In accordance with another aspect of the invention, the processing of the pipelines includes a first processing operation which detects target faults in a single time frame, and a second processing operation which detects target faults in two or more time frames. The first processing operation generates as many combinational test vectors as possible for each of the pipelines, while the second processing operation generates sequences of two or more combinational test vectors for each of the pipelines.
The invention in an illustrative embodiment utilizes a design for testability (DFT) technique, based on a combination of partial clock freezing and clock partitioning, to model a sequential circuit as a set of overlapping pipelines. The illustrative embodiment is particularly well-suited for use in performing automatic test pattern generation (ATPG) for sequential circuits.
Advantageously, the test pattern generation process of the present invention solves the problems associated with conventional testing of sequential circuits without requiring a scan-based DFT approach that significantly changes the structure of the circuit in test mode. The DFT technique utilized in the illustrative embodiment of the invention, which as noted above is based on a combination of partial clock freezing and clock partitioning, introduces no delay penalties and only a small area overhead, and it is compatible with at-speed testing. The clock freezing approach utilized by the invention is a partial clock freezing approach in that the only flip-flops (FFs) that are frozen are those that are required to be frozen in order to break feedback loops in the circuit. The remaining FFs not frozen in this partial freezing approach are part of transparent or capture registers in a given pipeline, and are thus not used for test generation in that pipeline. A significant advantage of the partial freezing approach of the present invention is that it provides an exponential reduction in the search space of an ATPG process.